(abridged) We present a new analysis of a large sample of quasar absorption-line spectra obtained using UVES (the Ultraviolet and Visual Echelle Spectrograph) on the VLT (Very Large Telescope) in Chile. In the VLT sample (154 absorbers), we find evidence that alpha increases with increasing cosmological distance from Earth. However, as previously shown, the Keck sample (141 absorbers) provided evidence for a smaller alpha in the distant absorption clouds. Upon combining the samples an apparent variation of alpha across the sky emerges which is well represented by an angular dipole model pointing in the direction RA=(17.3 +/- 1.0) hr, dec. = (-61 +/- 10) deg, with amplitude (0.97 +0.22/-0.20) x 10^(-5). The dipole model is required at the 4.1 sigma statistical significance level over a simple monopole model where alpha is the same across the sky (but possibly different to the current laboratory value). The data sets reveal a number of remarkable consistencies: various data cuts are consistent and there is consistency in the overlap region of the Keck and VLT samples. Assuming a dipole-only (i.e. no-monopole) model whose amplitude grows proportionally with `lookback-time distance' (r=ct, where t is the lookback time), the amplitude is (1.1 +/- 0.2) x 10^(-6) GLyr^(-1) and the model is significant at the 4.2 sigma confidence level over the null model [Delta alpha]/alpha = 0). We apply robustness checks and demonstrate that the dipole effect does not originate from a small subset of the absorbers or spectra. We present an analysis of systematic effects, and are unable to identify any single systematic effect which can emulate the observed variation in alpha.